Генетический алгоритм
Генети́ческий алгори́тм ( ) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (en:evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland), книга которого «Адаптация в естественных и искусственных системах» (1992)J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, 1975. является основополагающим трудом в этой области исследований. Описание алгоритма thumb|239px|Схема работы генетического алгоритма Задача кодируется таким образом, чтобы её решение могло быть представлено в виде вектора («хромосома»). Случайным образом создаётся некоторое количество начальных векторов («начальная популяция»). Они оцениваются с использованием «функции приспособленности», в результате чего каждому вектору присваивается определённое значение («приспособленность»), которое определяет вероятность выживания организма, представленного данным вектором. После этого с использованием полученных значений приспособленности выбираются вектора (селекция), допущенные к «скрещиванию». К этим векторам применяются «генетические операторы» (в большинстве случаев «скрещивание» — crossover и «мутация» — mutation), создавая таким образом следующее «поколение». Особи следующего поколения также оцениваются, затем производится селекция, применяются генетические операторы и т. д. Так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма. Таким критерием может быть: * нахождение глобального, либо субоптимального решения; * исчерпание числа поколений, отпущенных на эволюцию; * исчерпание времени, отпущенного на эволюцию. Генетические алгоритмы служат, главным образом, для поиска решений в очень больших, сложных пространствах поиска. Таким образом, можно выделить следующие этапы генетического алгоритма: # Создание начальной популяции # Определение (задание) функций приспособленности для особей популяции (оценивание) * (Начало цикла) :# Выбор индивидов из текущей популяции (селекция) :# Скрещивание и\или мутация :# Вычисление функций приспособленности для всех особей :# Формирование нового поколения :# Если выполняются условия останова, то (конец цикла), иначе (начало цикла). Создание начальной популяции Перед первым шагом нужно случайным образом создать некую начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей. Отбор На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Есть разные способы проводить отбор. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h). Сама доля выживших s обычно является параметром генетического алгоритма, и ее просто задают заранее. По итогам отбора из N особей популяции H должны остаться sN особей, которые войдут в итоговую популяцию H'. Остальные особи погибают. Размножение Размножение в генетических алгоритмах обычно половое — чтобы произвести потомка, нужны несколько родителей; обычно, конечно, нужны ровно два. Размножение в разных алгоритмах определяется по-разному — оно, конечно, зависит от представления данных. Главное требование к размножению — чтобы потомок или потомки имели возможность унаследовать черты обоих родителей, «смешав» их каким-либо достаточно разумным способом. Вообще говоря, для того чтобы провести операцию размножения, нужно выбрать (1-s)p/2 пар гипотез из H и провести с ними размножение, получив по два потомка от каждой пары (если размножение определено так, чтобы давать одного потомка, нужно выбрать (1 — s)p пар), и добавить этих потомков в H'. В результате H' будет состоять из N особей. Почему особи для размножения обычно выбираются из всей популяции H, а не из выживших на первом шаге элементов H0 (хотя последний вариант тоже имеет право на существование)? Дело в том, что главный бич многих генетических алгоритмов — недостаток разнообразия (diversity) в особях. Достаточно быстро выделяется один-единственный генотип, который представляет собой локальный максимум, а затем все элементы популяции проигрывают ему отбор, и вся популяция «забивается» копиями этой особи. Есть разные способы борьбы с таким нежелательным эффектом; один из них — выбор для размножения не самых приспособленных, но вообще всех особей. Мутации К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать mN особей, а затем изменить их в соответствии с заранее определенными операциями мутации. Применение генетических алгоритмов Генетические алгоритмы применяются для решения следующих задач: # Оптимизация функций # Оптимизация запросов в базах данных # Разнообразные задачи на графах (задача коммивояжера, раскраска, нахождение паросочетаний) # Настройка и обучение искусственной нейронной сети # Задачи компоновки # Составление расписаний # Игровые стратегии # Теория приближений # Искусственная жизнь # Биоинформатика (свёртывание белков) Пример тривиальной реализации на C++ Поиск в одномерном пространстве, без скрещивания. #include #include #include int main() { using namespace std; srand((unsigned)time(NULL)); const int N = 1000; int aN; //заполняем нулями fill(a, a+N, 0); for (;;) { //мутация в случайную сторону каждого элемента: for (int i = 0; i < N; ++i) if (rand()%2 1) ai += 1; else ai -= 1; //теперь выбираем лучших, отсортировав по возрастанию... sort(a, a+N); //... и тогда лучшие окажутся во второй половине массива. //скопируем лучших в первую половину, куда они оставили потомство, а первые умерли: copy(a+N/2, a+N, a /*куда*/); //теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше. cout << accumulate(a, a+N, 0) / N << endl; } } Примечания Ссылки * * Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с. * Научные статьи по генетическим алгоритмам * Genetic Algorithms in Ruby * Проект CuberGA — расширяемый framework для реализации генетических алгоритмов * Special Interest Group for Genetic and Evolutionary Computation (former ISGEC) * JAGA (Java API for Genetic Algorithms) — Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications in Java * IlliGAL (Illinois Genetic Algorithms Laboratory) Home Page * Evolutionary Computation Laboratory at George-Mason University * GENITOR Research Group (CS, Colorado) * Evolutionary and Adaptive Systems (EASy) at Sussex * Genetic Algorithms Articles * Evolutionary Algorithms Research Group at University of Dortmund * Evolutionary Digest Archive * Амёбы: «Эволюция искусственной жизни на Вашем ПК» * Эволюционные вычисления * Генетические алгоритмы * Генетические алгоритмы * Решение Диофантова уравнения * Подборка статей по теме Генетические алгоритмы * Основные операции генетического алгоритма * GAUL: Genetic Algorithm Utility Library — нетривиальная обобщенная свободная реализация GA * Реализация генетического алгоритма для .NET Framework 2.0 * Использование генетических алгоритмов в проблеме автоматического написания программ * Реализация генетических алгоритмов в среде MATLAB v6.12 * Сергей Николенко. Генетические алгоритмы (слайды) — лекция № 4 из курса «Самообучающиеся системы» * Очень большая подборка статей по использованию генетических алгоритмов в задачах многокритериальной оптимизации Категория:Эволюционные алгоритмы